public class HuffMinHeap {

	private int curr=0;
	private int len;
	private HuffNode[] a;
	
	
	public HuffMinHeap(HuffNode[] ra){
		a=ra;
		len=a.length;
		//heapMinSort(len);
		buildMinHeap(len);
	}
	
	public HuffMinHeap(HuffNode[] ra,int length){
		//main builder
		a=ra;
		len=length;
		buildMinHeap(len);
	}
	
	public void setFirstMin() throws Exception{
		throw new Exception("ss");
	}
	
	public HuffNode extractMin(){
		HuffNode ans=a[1];
		a[1]=new HuffNode(a[len].c,a[len].size,a[len].left,a[len].right);
		a[len].size=Integer.MAX_VALUE;
		len--;
		minHeapify(1, len);
		return ans;
	}
	
	public void insert(HuffNode key){
		
		len++;
		a[len].size=Integer.MAX_VALUE;
		a[len].c=0;
		decreaseKey(len, key);
		System.out.println("------inserting "+key.c+" ---------");
		//for (int i=1;i<len;i++)
			//System.out.println(a[i]);
	}	
	
	
	private void decreaseKey(int i,HuffNode key){
		a[i]=key;
		while (i>1 && a[i].compareTo(a[i/2])<0){
			//exchange
			HuffNode tmp=a[i];
			a[i]=a[i/2];
			a[i/2]=tmp;
			//
			i=i/2;
		}
	}
	
	public HuffNode getNextMin(){
		if (curr+1<=len){
			curr++;
			return a[curr];
		}
		else
			return null;
	}

	private void buildMinHeap(int n){
		for (int i=n/2;i>=1;i--){
			minHeapify(i, n);
		}
	}
	
	public void heapMinSort(int n){
		buildMinHeap(n);
		for (int i=n;i>=2;i--){
			//exchange
			HuffNode tmp=a[i];
			a[i]=a[1];
			a[1]=tmp;
			//minHeapify
			minHeapify(1,i-1);
		}
		for (int i=1;i<=len/2;i++){
			//exchange
			HuffNode tmp=a[i];
			a[i]=a[len-i+1];
			a[len-i+1]=tmp;
		}
		System.out.println("Done sorting");
	}
	
	
	private void minHeapify(int i,int n){
		int l=i*2;
		int r=l+1;
		int smallest=i;
		if (l<=n && (a[l].compareTo(a[smallest])<0)){
			smallest=l;
		}
		if (r<=n && (a[r].compareTo(a[smallest]))<0){
			smallest=r;
		}
		if (smallest!=i){
			//exchange
			HuffNode tmp=a[i];
			a[i]=a[smallest];
			a[smallest]=tmp;
			//minHeapify
			minHeapify(smallest,n);
		}
	}
	

	
	/*
		
		private void decreaseKey(HuffNode[] ra,int i,HuffNode key){
		ra[i]=key;
		while (i>1 && ra[i/2].size>ra[i].size){
			//exchange
			HuffNode tmp=ra[i];
			ra[i]=ra[i/2];
			ra[i/2]=tmp;
			//
			i=i/2;
		}
	}
	private void maxHeapify(int i){
		int l=i*2;
		int r=l+1;
		int largest=i;
		if (l<=currentSize && ra[l].size>ra[largest].size)
			largest=l;
		if (r<=currentSize && ra[r].size>ra[largest].size)
			largest=r;
		
		if (largest!=i){
			//exchange
			HuffNode tmp=ra[i];
			ra[i]=ra[largest];
			ra[largest]=tmp;
			//maxHeapify
			maxHeapify(largest);
		}
	}
	
	public HuffNode extractMin(){
		HuffNode min=ra[1];
		ra[1]=ra[currentSize];
		currentSize--;
		minHeapify(1);
		return min;
	}
	
	
	public void insert(HuffNode ins){
		if (currentSize<maxSize){
			currentSize++;
			ra[currentSize].size=Integer.MAX_VALUE;
			decreaseKey(currentSize, ins);
		}
		
	}
	
	private void buildFromArray(HuffNode[] data) throws Exception{
		if (data==null || ra==null || data.length>=ra.length)
			throw new Exception("check buildFromArray");
		else{
			for (int i=1; i<=data.length;i++){
				ra[i]=data[i];
			}
			currentSize=data.length;
		}
	}
*/
	
}
